Grokking Oracle Coding Interview
Rate this course
Ask Author
Contribute
Back to course home

0% completed

Vote For New Content
Introduction
Who Should Take This Course?
Oracle Easy
Count Number of Pairs With Absolute Difference K (easy)
Solution: Count Number of Pairs With Absolute Difference K
Degree of an Array (easy)
Solution: Degree of an Array
Find Subsequence of Length K With the Largest Sum (easy)
Solution: Find Subsequence of Length K With the Largest Sum
Rectangle Overlap (easy)
Solution: Rectangle Overlap
Remove All Adjacent Duplicates In String (easy)
Solution: Remove All Adjacent Duplicates In String
Island Perimeter (easy)
Solution: Island Perimeter
Climbing Stairs (easy)
Solution: Climbing Stairs
Move Zeroes (easy)
Solution: Move Zeroes
Excel Sheet Column Title (easy)
Solution: Excel Sheet Column Title
Valid Parentheses (Easy)
Solution: Valid Parentheses
Oracle Medium
Longest Palindromic Substring (medium)
Solution: Longest Palindromic Substring
Single Element in a Sorted Array (medium)
Solution: Single Element in a Sorted Array
Pairs of Songs With Total Durations Divisible by 60 (medium)
Solution: Pairs of Songs With Total Durations Divisible by 60
Search a 2D Matrix II (medium)
Solution: Search a 2D Matrix II
Minimize Maximum of Array (medium)
Solution: Minimize Maximum of Array
Asteroid Collision (medium)
Solution: Asteroid Collision
Combination Sum (medium)
Solution: Combination Sum
Binary Tree Right Side View (medium)
Solution: Binary Tree Right Side View
Sort Colors (medium)
Solution: Sort Colors
Group Anagrams (Medium)
Solution: Group Anagrams
Decode String (Medium)
Solution: Decode String
Number of Islands (medium)
Solution: Number of Islands
Binary Tree Zigzag Level Order Traversal (medium)
Solution: Binary Tree Zigzag Level Order Traversal
Longest Common Subsequence (medium)
Solution: Longest Common Subsequence
Rotting Oranges (medium)
Solution: Rotting Oranges
Meeting Rooms II (medium)
Solution: Meeting Rooms II
Delete Node in a BST (medium)
Solution: Delete Node in a BST
Remove Duplicate Letters (medium)
Solution: Remove Duplicate Letters
Longest Substring Without Repeating Characters (medium)
Solution: Longest Substring Without Repeating Characters (medium)
Search in Rotated Array (medium)
Solution: Search in Rotated Array
Spiral Matrix (medium)
Solution: Spiral Matrix
Container With Most Water (Medium)
Solution: Container With Most Water
3Sum (medium)
Solution: 3Sum
Simplify Path (medium)
Solution: Simplify Path
Next Permutation (medium)
Solution: Next Permutation
Basic Calculator II (medium)
Solution: Basic Calculator II
Merge Intervals (medium)
Solution: Merge Intervals
Restore IP Addresses (medium)
Solution: Restore IP Addresses
Longest Increasing Subsequence (medium)
Solution: Longest Increasing Subsequence
Validate Binary Search Tree (medium)
Solution: Validate Binary Search Tree
Integer to English Words (hard)
Solution: Integer to English Words
Trapping Rain Water (hard)
Solution: Trapping Rain Water
First Missing Positive (hard)
Solution: First Missing Positive
Merge K Sorted Lists (hard)
Solution: Merge K Sorted Lists
Max Points on a Line (hard)
Solution: Max Points on a Line
Sudoku Solver (hard)
Solution: Sudoku Solver
Longest Valid Parentheses (hard)
Solution: Longest Valid Parentheses
Remove Nth Node From End of List (Medium)
Solution: Remove Nth Node From End of List
Median of Two Sorted Arrays (hard)
Solution: Median of Two Sorted Arrays
Constrained Subsequence Sum (hard)
Solution: Constrained Subsequence Sum
Solution: Restore IP Addresses

Problem Statement

Given a string s containing digits only, return a list of string containing the valid ip addresses that can be formed by inserting the dots(.) in between string characters.

A valid IP address consists of four parts, each ranging from 0 to 255, separated by dots. It's important to note that leading zeros in any part of the IP address are not allowed, except for the number 0 itself.

  • For example, "1.1.21.1", and "1.12.1.1" are valid ip addresses, and "1.1.021.1" is invalid ip address.

Examples

  • Example 1:

    • Input: "11211"
    • Expected Output: ["1.1.2.11", "1.1.21.1", "1.12.1.1", "11.2.1.1"]
    • Justification: These are all the valid ways to insert dots into the input string such that each segment forms a valid part of an IP address without leading zeros, except for the number 0 itself, and each segment is within the range of 0 to 255.
  • Example 2:

    • Input: "1111"
    • Expected Output: ["1.1.1.1"]
    • Justification: Based on the string's length and value, there is only one way to form a valid IP address by inserting dots after each digit.
  • Example 3:

    • Input: "0000"
    • Expected Output: ["0.0.0.0"]
    • Justification: Despite leading zeros being generally disallowed, in this case, each segment of the IP address is the number 0 itself, making it the only valid formation.

Solution

To solve this problem, we employ a backtracking algorithm, which is a form of recursive search. The idea is to explore all possible combinations of dots that could be inserted into the original string to form valid IP addresses. We choose backtracking because it allows us to explore each possibility and backtrack if the current path doesn't lead to a valid solution, making it highly suitable for this problem. This approach is effective because it systematically covers all potential combinations and efficiently prunes paths that violate the constraints of a valid IP address, such as parts being greater than 255 or having leading zeros.

The backtracking process involves recursively placing dots in the string and validating each part formed. If a part is valid (0 through 255 and no leading zeros unless the part is exactly '0'), the algorithm proceeds to the next part. This continues until either four valid parts are created, indicating a valid IP address, or it becomes impossible to form a valid address, at which point the algorithm backtracks to explore other possibilities.

Step-by-step Algorithm

  1. Initialize an empty list to store the valid IP addresses.

  2. Start the backtracking process with the initial parameters: the string s, position 0 in the string, an empty current IP address string, and a dot count of 0.

  3. In the backtracking function:

    • Check for base condition: If the end of the string is reached and exactly 4 segments (indicated by 3 dots) are found, remove the last dot from the current IP address string and add it to the result list.
    • Stop the recursion if more than 4 segments are found or the end of the string is reached without completing 4 segments.
  4. Iterate over the next 1 to 3 characters of the string from the current position:

    • Skip invalid segments: Segments starting with '0' followed by more digits or segments representing numbers greater than 255.
  5. For each valid segment:

    • Add the segment and a dot to the current IP address string.
    • Recursively call the backtracking function with the new position, updated current IP address string, and incremented dot count.
  6. Repeat the process until all possible combinations are explored.

  7. Return the list of valid IP addresses after exploring all possibilities.

Step-by-Step Walkthrough

For the input "11211".

  1. Start with an empty path and result list.

    • path = [], result = [], start = 0
  2. First Recursive Call (First Octet)

    • Try with 1 character: "1"
      • path = ["1"], valid, proceed.
      • Recursive call with start = 1.
  3. Second Recursive Call (Second Octet)

    • From "1211", try with 1 character: "1"
      • path = ["1", "1"], valid, proceed.
      • Recursive call with start = 2.
  4. Third Recursive Call (Third Octet)

    • From "211", try with 1 character: "2"
      • path = ["1", "1", "2"], valid, proceed.
      • Recursive call with start = 3.
  5. Fourth Recursive Call (Fourth Octet)

    • From "11", try with 2 characters: "11" (as 1 character "1" is too short to consume the rest of the string for a valid IP)
      • path = ["1", "1", "2", "11"], valid, and it's the end of the string.
      • Add to result: "1.1.2.11".
  6. Backtrack to Complete Third Recursive Call

  • Backtrack to third octet starting point after adding "11" as the fourth octet.
    • Previously we had path = ["1", "1", "2"] and successfully added "11" for the fourth octet.
    • Now, backtrack to explore other possibilities for the third and fourth octets with the remaining "211".
  1. Explore New Combination for Third and Fourth Octets
  • Attempt to use "21" as the third octet.
    • Modify path to ["1", "1", "21"], leaving "1" for the fourth octet.
    • This is a valid octet, so proceed to check the fourth octet.
    • Add "1" as the fourth octet, forming path = ["1", "1", "21", "1"].
    • Add to result: "1.1.21.1".
  1. Backtrack Again for Other Combinations
  • Backtrack to the point of choosing the third octet again, this time considering "211" entirely for the third and fourth octets.
    • It's realized that "211" as a single segment is not possible due to the constraint of having four segments.
    • Thus, no further action here.
  1. Backtrack to Second Octet
  • Backtrack to explore more combinations by changing the second octet.
    • Change the second octet from "1" to "12", leaving "11" for the third and fourth octets.
    • path now becomes ["1", "12"].
  1. Explore Combinations with "12" as the Second Octet
  • With "12" as the second octet and "11" remaining, try "1" as the third octet.
    • path becomes ["1", "12", "1"], leaving "1" for the fourth octet.
    • This is valid; add "1" as the fourth octet, forming path = ["1", "12", "1", "1"].
    • Add to result: "1.12.1.1".
  1. Attempt All Combinations Starting with "11" as the First Octet
  • Consider "11" as the first octet and proceed to explore all possible combinations for the remaining "211".
    • First, try "2" as the second octet and "1" as the third, leaving "1" for the fourth.
      • path becomes ["11", "2", "1", "1"].
      • Add to result: "11.2.1.1".
    • Explore other combinations, but realize other splits either exceed the octet value limit or don't fill all four octets properly.
  1. Final Result
  • After systematically exploring and backtracking through all possible splits, the algorithm concludes with the final result list containing all valid IP addresses that can be formed from "11211":
    • ["1.1.2.11", "1.1.21.1", "1.12.1.1", "11.2.1.1"]

Code

Java

. . . .

Complexity Analysis

  • Time Complexity: The algorithm has a time complexity of , where N is the length of the input string. This is because, in the worst case, the algorithm explores 3 options (1, 2, or 3 digits) for each of the 4 parts of the IP address.
  • Space Complexity: The space complexity is due to the recursion stack depth, which could go up to N in the worst case, plus the space needed to store the valid IP addresses.
Restore IP Addresses (medium)
Longest Increasing Subsequence (medium)
Mark as Completed

On this page

Problem Statement

Examples

Solution

Step-by-step Algorithm

Step-by-Step Walkthrough

Code

Complexity Analysis